"""
377. 组合总和 Ⅳ
https://leetcode.cn/problems/combination-sum-iv/description/

难度：中等

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

输入：nums = [9], target = 3
输出：0


提示：

1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000


进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？
"""
from typing import List


class Solution:
    
    """
    定义dp数组，dp[i][j]表示最一个数可以为coins[0]~coins[i], 和为j的排列组合数，
    即dp[0][j]表示最后一个数只能是coins[0]，dp[1][j]最后一个数可以是coins[0]和coins[1]
    所以此时dp[i][j] = dp[i-1][j] + dp[-1][j-coins[i]]
    
    即：最后一个数为coins[i]的状态数 加上 最后一个数不为coins[i]的状态数。
    
    由于状态转移方程中依赖前面列的最后一行的状态，即所有硬币面额的排列组合数，
    所以需要在内层遍历硬币面额。
    """

    # 方法一：动态规划
        
    def combinationSum4(self, nums: List[int], target: int) -> int:
        # 1. 定义dp数组
        dp = [[0] * (target + 1) for _ in range(len(nums))]
        # 2. 初始化dp数组
        for i in range(len(nums)):
            dp[i][0] = 1  # 数据的起点，无意义
        # 3. 递推公式 完全背包
        for j in range(1, target+1):
            for i in range(len(nums)):
                if nums[i] > j:  # 剪枝
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[-1][j-nums[i]] + dp[i-1][j]
        return dp[-1][-1]
    
    # 思路2：
    # 暴力:只有一个硬币时几种排列，有两种硬币时几种排列，..., n种硬币时几种排列

    
if __name__ == "__main__":
    s = Solution()
    nums = [1,2,3]
    target = 4

    n = s.combinationSum4(nums, target)
    print(n)